package com.zxy.leetcode._00000_00099._00000_00009;

/**
 * https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
 *
 * 寻找两个正序数组的中位数
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
 *
 * 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
 *
 * **未通过**
 */
public class Test00004 {

    public static void main(String[] args) {
        int[] num1 = {1, 3, 5, 7, 9};
        int[] num2 = {2, 4, 6, 8, 10};
        int[] num3 = {2, 4, 6, 8};
        Test00004 test = new Test00004();
        System.out.println(test.findMedianSortedArrays(num1, num2));
        System.out.println(test.findMedianSortedArrays(num1, num3));
        System.out.println(test.findMedianSortedArrays(num2, num3));

        int[] num4 = {1};
        int[] num5 = {3, 4, 5};
        System.out.println(test.findMedianSortedArrays(num4, num5));

        int[] num6 = new int[100];
        int[] num7 = new int[200];
        for (int i=0; i<100; i++) {
            num6[i] = 3 * i;
            num7[2 * i] = 3 * i + 1;
            num7[2 * i + 1] = 3 * i + 2;
        }
        System.out.println(test.findMedianSortedArrays(num6, num7));
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int k = (len1 + len2)/2;
        if ((len1 + len2) % 2 == 1) {
            return findKth(nums1, nums2, k + 1);
        }else {
            int kth = findKth(nums1, nums2, k);
            int k1th = findKth(nums1, nums2, k+1);
            return (kth + k1th) / 2.0d;
        }
    }

    /**
     *
     * @param nums1
     * @param nums2
     * @param k     第K小的元素
     * @return
     */
    public static int findKth(int[] nums1, int[] nums2, int k) {
        int p1Left = 0;
        int p1Right = nums1.length - 1;
        int p2Left = 0;
        int p2Right = nums2.length - 1;

        while (true) {
            if (p1Left > p1Right) {
                return nums2[p2Left + (k-1)];
            }
            if (p2Left > p2Right) {
                return nums1[p1Left + (k-1)];
            }

            if (k == 1) {
                return Math.min(nums1[p1Left], nums2[p2Left]);
            }
            if (k < 4) {
                int n1 = nums1[p1Left];
                int n2 = nums2[p2Left];
                if (n1 <= n2) {
                    k --;
                    p1Left ++;
                    continue;
                }else {
                    k --;
                    p2Left ++;
                    continue;
                }
            }

            int p1Mid = Math.min(p1Left + k/2, (p1Left + p1Right)/2);
            int p2Mid = Math.min(p2Left + k/2, (p2Left + p2Right)/2);

            if (nums1[p1Mid] <= nums2[p2Mid]) {
                // 舍弃（p1Mid - p1Left）个数据，这些数据肯定比第k小还小
                if (p1Mid == p1Left) {
                    p1Mid ++;
                }
                k -= p1Mid - p1Left;
                p1Left = p1Mid;
            }else {
                if (p2Mid == p2Left) {
                    p2Mid ++;
                }
                k -= p2Mid - p2Left;
                p2Left = p2Mid;
            }
        }
    }

}
